package club.vann.nowcoder;

import club.vann.nowcoder.common.ListNode;

import java.util.List;

/**
 * <p>难度：Easy</p>
 * <p>题目：两个链表的第一个公共节点</p>
 * <p>描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-23:08:48:22
 */
public class NC66 {
    public static void main(String[] args) {
        NC66 nc66 = new NC66();
        ListNode[] nodes = null;

        nodes = TestCase.fun();
        System.out.println(nc66.FindFirstCommonNode(nodes[0], nodes[1]));

        nodes = TestCase.fun1();
        System.out.println(nc66.FindFirstCommonNode(nodes[0], nodes[1]));

        nodes = TestCase.fun2();
        System.out.println(nc66.FindFirstCommonNode(nodes[0], nodes[1]));
    }

    /**
     * 解法一：
     *
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode node1 = pHead1, node2 = pHead2;
        while(node1 != node2) {
            node1 = (node1 == null) ? pHead2 : node1.next;
            node2 = (node2 == null) ? pHead1 : node2.next;
        }
        return node1;
    }

    static class TestCase {
        public static ListNode[] fun() {
            ListNode[] nodes = new ListNode[2];
            ListNode head1 = new ListNode(1);
            ListNode head2 = new ListNode(7);

            nodes[0] = head1;
            nodes[1] = head2;

            head1.next = new ListNode(2);
            head2.next = new ListNode(8);
            head1 = head1.next;
            head2 = head2.next;

            head1.next = new ListNode(3);
            head2.next = new ListNode(9);
            head1 = head1.next;
            head2 = head2.next;

            head1.next = new ListNode(4);
            head2.next = new ListNode(5);
            head1 = head1.next;
            head2 = head2.next;
            head1.next = head2;
            head1 = head1.next;

            head1.next = new ListNode(6);
            return nodes;
        }

        public static ListNode[] fun1() {
            ListNode[] nodes = new ListNode[2];
            ListNode head1 = new ListNode(1);
            ListNode head2 = new ListNode(6);
            nodes[0] = head1;
            nodes[1] = head2;

            head1.next = new ListNode(2);
            head1 = head1.next;
            head1.next = new ListNode(3);
            head1 = head1.next;
            ListNode pubNode = new ListNode(4);
            head1.next = pubNode;
            head1 = head1.next;
            head1.next = new ListNode(5);


            head2.next = new ListNode(7);
            head2 = head2.next;
            head2.next = new ListNode(8);
            head2 = head2.next;
            head2.next = pubNode;

            return nodes;
        }

        public static ListNode[] fun2() {
            ListNode[] nodes = new ListNode[2];
            ListNode head1 = new ListNode(1);
            ListNode head2 = new ListNode(2);
            nodes[0] = head1;
            nodes[1] = head2;

            ListNode cur1 = head1;
            ListNode cur2 = head2;
            cur1.next = new ListNode(3);
            cur2.next = cur1.next;

            return nodes;
        }
    }
}
